Skip to main content

Full text of "Stopping Sets of Algebraic Geometry Codes"

See other formats


m 



< 
(N 



Stopping Sets of Algebraic Geometry Codes 

Jun Zhang, Fang-Wei Fu and Daqing Wan 



Abstract 

Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis 

of iterative decoding for this linear code. Let C be an [n, k] linear code over F^ with parity-check matrix H, where 

the rows of H may be dependent. Let [n] = {1, 2, • • • ,n} denote the set of column indices of H. A stopping set 

S of C with parity-check matrix iJ is a subset of [n] such that the restriction of H to S does not contain a row of 

(<— ^ , weight 1. The stopping set distribution {Ti(iJ)}"^Q enumerates the number of stopping sets with size i of C with 

CN I parity-check matrix H. Denote H* the parity-check matrix consisting of all the non-zero codewords in the dual 

Jh ' code C^. In this paper, we study stopping sets and stopping set distributions of some residue algebraic geometry 

(AG) codes with parity-check matrix H*. First, we give two descriptions of stopping sets of residue AG codes. 

For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. 

Then we consider AG codes from elliptic curves. We use the group structure of rational points of elliptic curves to 

present a complete characterization of stopping sets. Then the stopping sets, the stopping set distribution and the 

stopping distance of the AG code from an elliptic curve are reduced to the search, counting and decision versions 

of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special 

t/3 ' cases, we determine the stopping set distributions of AG codes from elliptic curves. 

Index Terms 

^ ' Stopping sets, stopping set distribution, stopping distance, algebraic geometry codes, elliptic curves, subset 

f— ^ . sum problem. 

■^ '■ I. Introduction 

O 

Let C be an [n, k, d] linear code over F^ with length n, dimension k and minimum distance d. Let H 

j> be a parity-check matrix of C, where the rows of H may be dependent. Let [n] = {1, 2, ■ ■ ■ , n} denote 

/\ the set of column indices of H. A stopping set S of C with parity-check matrix iJ is a subset of [n] such 
H ■ 

that the restriction of H to S, say H{S), does not contain a row of weight I. The stopping set distribution 

{Ti{H)}1^Q enumerates the number of stopping sets with size i of C with parity-check matrix H. Note 

that the empty set is defined as a stopping set and Tq{H) = L A number of researchers have recently 

studied the stopping sets and stopping set distributions of linear codes, e.g., see [1, 2, 5-18, 20, 21, 24- 

26, 28, 32-36]. Stopping sets and stopping set distribution of a linear code are used to determine the 

performance of this linear code under iterative decoding [5]. 

The first two authors are supported by the National Key Basic Research Program of China (973 Grant No. 2013CB834204), and the 
National Natural Science Foundation of China (Nos. 61171082, 10990011 and 60872025). This paper was presented in part at the 9th 
Annual Conference on Theory and Applications of Models of Computation, Turing Centenary Meeting, Chinese Academy of Sciences, 
Beijing, China, May 16-21, 2012. 

Jun Zhang is with the Chem Institute of Mathematics, Nankai University, Tianjin, 300071, P.R. China, e-mail: 
zhangj un04 @ mail .nankai . edu. en 

Fang-Wei Fu is with the Chem Institute of Mathematics and LPMC, Nankai University, Tianjin, 300071, P.R. China, e-mail: 
fwfu@nankai.edu.cn 

Daqing Wan is with the Department of Mathematics, University of California, Irvine, CA 92697-3875, USA. e-mail: dwan@math.uci.edu 



cd 



The stopping distance s{H) of C with the parity-check matrix H is the minimum size of nonempty 
stopping sets. It plays an important role in the performance analysis of the iterative decoding, just as the role 
of the minimum Hamming distance dof a code for maximum-likehood or algebraic decoding. Analogously 
to the redundancy of a linear code, Schwartz and Vardy [28] introduced the stopping redundancy p{C), 
the minimal number of rows in the parity-check matrix H for the linear code C such that the stopping 
distance s{H) = d, to characterize the minimal "complexity" of the iterative decoding for the code C. 
The stopping redundancy of some linear codes such as Reed-MuUer codes, cyclic codes and maximal 
distance separable (MDS) codes have been studied recently [8, 11-13, 28]. 

Note that the stopping distance, the stopping sets and stopping set distribution depend on the choice 
of the parity-check matrix H of C. Recall that H* is the parity-check matrix consisting of all non-zero 
codewords in the dual code C^. For any parity-check matrix H, it is obvious that Ti{H) ^ Ti{H*) for 
all i, since iJ is a sub-matrix formed by some rows of H* . Although the iterative decoding with the 
parity-check matrix H* has the highest decoding complexity, it achieves the best possible performance 
as it has the smallest stopping set distribution. It is known from [34] and [16] that the iterative decoding 
with the parity-check matrix H* is an optimal decoding for the binary erasure channel. The stopping 
set distribution is used to characterize the performance under iterative decoding. So it is important to 
determine the stopping set distribution of C with the parity-check matrix H* . However, in general, it 
is difficult to determine the stopping set distribution of C with the parity-check matrix H* . Using finite 
geometry, Jiang et al. [17] gave characterizations of stopping sets of some Reed-MuUer codes (the Simplex 
codes, the Hamming cods, the first order Reed-MuUer codes and the extended Hamming codes). And they 
determined the stopping set distributions of these codes. Since the iterative decoding with parity-check 
matrix H* has the highest decoding complexity, they [17] considered a parity-check matrix H, a submatrix 
of H*, such that the stopping set distribution of C with parity-check matrix H is the same as that with 
H*, but has the smallest number of rows. Such a parity-check matrix H is called optimal in certain sense. 
In general, it is difficult to obtain an optimal parity-check matrix for a general linear code. In [17], they 
obtained optimal parity-check matrices for the Simplex codes, the Hamming cods, the first order Reed- 
MuUer codes and the extended Hamming codes. They also proposed an interesting problem to determine 
the stopping set distributions of well known linear codes with the parity-check matrix H*. In this paper, 
we consider AG codes and a specific class of AG codes, i.e., AG codes associated with elliptic curves. 

From now on, we always choose the parity-check matrix H* for linear codes in this paper It is well- 
known that 

Proposition 1 ([28]). Let C be a linear code with minimum distance d{C), and let H* denote the parity- 
check matrix for C consisting of all the nonzero codewords of the dual code C-^. Then the stopping 
distance s{H*) = d{C). 



Note that the generalized Reed-Solomon codes are MDS codes. For the [n, k, d] MDS code C, i.e., 
d = n — k + 1, its dual code C"*- is still an [n,n — k,k + 1] MDS code. Since any non-zero codeword in 
C"*- has at most n — k — I zeros and any (n — k) positions form an information set, we have 

Proposition 2. Let C be an [n,k,n — k + 1] MDS code. Then 

(i) any subset of [n] with cardinality ^ n — k + 1 is a stopping set; 

(ii) any non-empty subset of [n] with cardinality ^ n — k is not a stopping set. 

By Proposition 2, we obtain the stopping set distribution of MDS codes. 

Corollary 3. Let C be an [n,k,n — k + l] MDS code. Then the stopping set distribution of C is given by 

[ 1, if^ = ^, 
Ti{H*) = I 0, ifl^i^n-k, 
[ (^), ift^n-k + 1. 

As a generalization of the generalized Reed-Solomon codes, next we study the stopping sets and 
stopping set distributions of AG codes. 

Constructions of AG codes. 

Without more special instructions, we fix some notation valid for the entire paper. 

• X/¥g is a geometrically irreducible smooth projective curve of genus g over the finite field ¥g with 
function field ¥g{X). 

• X{¥q) is the set of all ¥ q-rational points on X. 

• D = {Pi, P2, ■ ■ ■ , Pn} is a proper subset of X(¥q). 

• Without any confusion, also write D = Pi + P2 + ■ ■ ■ + Pn- 

• G is a divisor of degree m (2g — 2 < m < n) with Supp(G') H D = 0. 

Let y be a divisor on X. Denote by ^(V) the F^-vector space of all rational functions / G ¥q(X) with 
the principal divisor div(/) ^ —V, together with the zero function. And Denote by n(y) the Fg- vector 
space of all the Weil differentials cu with divisor div(a;) ^ V, together with the zero differential (cf. [31]). 
For any Fg -rational point P on X, choose one uniformizer t for P. Then for any differential cu, we can 
write cu = udt with some u E ¥q(X). Write the P-adic expansion u = Xli^j '^j^* f^^ some io E Z and 
ai E ¥q, the residue map of cu at the point P is defined to be 

resp{uj) = resp^tiu) = a_i. 

One can show that the above definition is well-defined [31, Proposition 4.2.9]. 

The residue AG code Cn{D, G) is defined to be the image of the following residue map: 



res: n{G - D) -^ F^ 

Lu ^ {resp^{u),resp^{u),--- ,resp„{u)) . 






And its dual code, the functional AG code C^{D, G) is defined to be the image of the following evaluation 
map: 

They are linear codes over F^, and have the code parameters [n,n — m + g — l,d ^ m — 2g + 2] and 
[n, m—g+l, d ^ n—m], respectively. And they can be represented from each other [31, Proposition 8.1.2]. 

For the simplest AG codes, i.e., the generalized Reed-Solomon codes, we have determined all the 
stopping sets. Then we consider the AG codes Cq{D,G) from elliptic curves. In this case, using the 
Riemann-Roch theorem, the stopping sets can be characterized completely as follows. 

Main Theorem. Let E be an elliptic curve over F^, D = {Pi,P2, ■ ■ ■ ,P„} a subset of E{¥q) such 
that the zero element O ^ D and let G = mO (0 < m < n). The non-empty stopping sets of the residue 
code Gq{D,G) are given as follows: 

(i) Any non-empty subset of [n] with cardinality ^ m — 1 is not a stopping set. 

(ii) Any subset of [n] with cardinality ^ m + 2 is a stopping set. 

(iii) AC [n], ^A = m + 1, is a stopping set if and only if for all i E A, the sum 

jeA\{i} 
(iv) AC [n], ^A = m, is a stopping set if and only if 

jeA 
(v) Denote by S{m) and S{m + 1) the two sets of stopping sets with cardinality m and m + 1 in 
the cases (iv) and (iii), respectively. Let 

^+(m)= U {AU{i}:ie [n]\A} . 

Then the union in ^^(m) is a disjoint union, and we have 

S{m + l)r\S+{m) =(lS , 

and 

S'(m + 1) = {all subsets of [n] with cardinalitym + 1} \ S^{m) . 

The proof will be given in Section 3. By this theorem, the stopping set distribution of Cq{D, G) follows 
immediately. 

Theorem 4. Notation as above. The stopping set distribution of Cq{D,G) with the parity-check matrix 



H* is 



ifi = 0, 

if 1 ^ i ^ m — 1, 

if i = m, 

if i = m + 1, 

if i ^ m + 2 . 



1, 

0, 

Ui)-(n-m)#5(m), 

Then by Theorem 4, we easily see that the stopping distance of Cn{D, G) is m or m+ 1. But to decide 
it is equivalent to a decision version of m-subset sum problem [19, 22, 23] in the group E(¥g), which 
is an NP-hard problem under RP-reduction [3]. Hence to compute the stopping distance of Cq{D, G) is 
NP-hard under RP-reduction. To compute the stopping set distribution is a counting version of m-subset 
sum problem in the group E{¥g), so it is also an NP-hard problem. But for a special D C E{¥g) with 
strong algebraic structure, it is possible to compute the complete stopping set distribution. For instance, 
if we take D = P\ {O}, where P is a subgroup of E(¥q). In particular, in application we always choose 
D = E{¥g) \ {0} to get a long linear code which is called standard elliptic code. Denote A^ = \P\ the 
cardinality of P, exp(P) the exponent of P, P[d] the rf-torsion subgroup of P, and 

1 >r^ , . . ™ , , ™ , fN/s - r 

\m/s\ 



N{m) 



s\ exp(P) 



-1) 



m+LfJ 



d\s 



fi{s/d)i^P[d] , 



ifi = 0, 

if 1 ^ i ^ m ~ 1, 

if i = m, 

if i = m + 1, 

if i^ m + 2 . 



respectively. It is known from [19, 23] that ^S{m) = N{m). Hence, we have 

Theorem 5. Let D = P\{0}, where P is a subgroup of E{¥q). The stopping set distribution ofGn{P>, G) 
with the parity-check matrix H* is 

{ ^' 

0, 

T,{H*) = I N{m), 

This paper is organized as follows. In Section 2, we study stopping sets of an arbitrary AG code 
and give algebraic and geometric descriptions of stopping sets. In Section 3, we study the stopping sets 
and stopping set distributions of AG codes Cq{D, G) from elliptic curves. We use the group structure of 
rational points of elliptic curves to present a complete characterization of stopping sets. It is shown that the 
stopping sets, the stopping set distribution and the stopping distance of the AG code from an elliptic curve 
can be reduced to the search, counting and decision versions of the subset sum problem in the group 
of rational points of the elliptic curve, respectively. We present the counting formula for the stopping 
set distributions of AG codes from elliptic curves. In particular, for some special cases, we determine 
explicitly the stopping set distributions of AG codes from elliptic curves. Finally, some conclusions and 
open problems are given in Section 4. 



II. Stopping Sets of Algebraic Geometry Codes 

Let X/Fg be a geometrically irreducible smooth projective curve of genus g over the finite field ¥g with 
function field ¥g(X), and Cfi{D, G) the residue AG code from X. In this section, we study stopping sets 
and stopping set distributions of general residue AG codes and give algebraic and geometric descriptions 
of the stopping sets of Cfi{D, G). 

Theorem 6. A subset A C [n] is a stopping set of Cn{D, G) if and only if 

^{g-J2p,) = [j^{g- J2 p^)- 

jeA ieA j&A\{i} 

Proof: By the definition, A C [n] is not a stopping set of Gn{D,G) if and only if there is some 
f e^{G) such that 

ev{f)\A = {fim^eA 

has weight 1. That is, there is some i E A such that 

f{Pi)^0 and f{P,) = for all J e A\{t} . 
This is equivalent to saying that 

j&A\{i} jeA 

So A is a stopping set if and only if for any i E A, 

jeA jeA\{i} 

Since ^{G - Zj^a Pj) ^ ^(^ - EjeA^ Pj) for any t E A, we have 

-^{G - Y^jeA Pj) = UieA -^(G - Y.jeA\{i} Pj) 
^^ ^{G - Y.,eA Pj) = ^{G - EjeAm P,) for any i E A. 
So the theorem holds. ■ 

As a simple corollary, we obtain 

Corollary 7. (i) Any subset of [n] with cardinality ^ m + 2 is a stopping set of Gq{D, G). 

(ii) Any non-empty subset of [n] with cardinality ^ m — 2g + 1 is not a stopping set of Gq{D, G). 

Proof: (i) For any subset A C [n] with cardinality ^ m+2, divisors C — ^ g^wo Pj and G — ^-^^ Pj 
are negative. So 

^{G-j2Pj) = [j^{G- J2 p^) = w- 

j€A i€A iGA\{j} 

It follows from Theorem 6 that A is a stopping set. 



(ii) For any non-empty subset A C [n] with cardinality ^ m — 2g + l,hy the Riemann-Roch theorem 
we have 

dimi-^iG-EjeAPj)) = m-#A-g + l, 
dim(^(G-E,eA\«^.)) = m-i^A-g + 2. 

So 

jdA 3&A\{i} 

for all i E A.li follows from Theorem 6 that A is not a stopping set. Note that one can also give another 
proof of (ii) from Proposition 1, since the minimum distance of Cn{D, G) is at least m — 2g + 2. ■ 

If we represent the generalized Reed-Solomon codes as AG codes from the rational function field, then 
by Corollary 7, we also obtain Proposition 2 for the generalized Reed-Solomon codes. 

Using the Riemann-Roch theorem, we give another description of stopping sets of AG codes Cn{D, G). 

Theorem 8. A subset A C [n] is a stopping set of Gn{D, G) if and only if for any i E A, there exists an 
effective divisor Ei with Pi ^ Supp(ii^j) such that 

K-G + J2P3-E^^ 

jeA 

where K is a canonical divisor on X and ~ means that two divisors are linearly equivalent, i.e., the 
difference between the two divisors is a principal divisor 

Proof: From the proof of Theorem 6, a subset A C [n] is a stopping set if and only if for any i G A, 

dim^(G - J2 P]) = dim^{G - ^ Pj) . 

jeA jeA\{i} 

The Riemann-Roch theorem states that for any divisor V, we have 

dim^(\/) = deg(\/) - ^ + 1 + dim^{K - V) . 
So a subset A C [n] is a stopping set if and only if for any i E A, 

dim^{K -G + J2Pj) = dim^{K -G+ J^ ^j) + ^ • 

jeA j&A\{i} 

It is equivalent to that for any i E A, there exists 

jeA jeA\{i} 

The last statement is equivalent to that for any i e A, there exists an effective divisor E^ with Pi ^ 



Supp(-Ei) such that 

Indeed, E^ = div(/) + K-G + ^jeA Pj- ■ 

By Theorem 8, we immediately have a sufficient condition for a subset to be a stopping set. 

Corollary 9. Keep notation as above. Let A be a subset of [n]. If K — G + J2jeA Pj ~ -^ f^^ some 
effective divisor E whose support has no intersection with {Pi\i E A}, then A is a stopping set. 

III. Stopping Sets and Stopping set Distributions of AG Codes from Elliptic Curves 

In the previous section, for the general AG code Cq{D, G), we have seen that there is a gap, deg(G') — 
2g + 2 ^ i ^ deg(G') + 1, where in general we have not determined whether a subset with cardinality i 
is a stopping set or not. In this section, we consider a class of special AG codes, AG codes constructed 
from elliptic curves. 

Let X = E he an elliptic curve over the finite field F^ with a rational point O. Endow E(¥q) a group 
structure with the zero element O. Let D = {Pi, P2, ■ ■ ■ , Pn} be a subset of the set E(¥q) such that 
O ^ D.let G = mO (0 < m < n). 

In general, if G is a divisor of degree m on E, then for any rational point Q E E{¥g), as deg{G — 
[m — l)Q) = 1, by the Riemann-Roch theorem, there exists one and only one rational point P E E(¥g) 
such that G ~ (m — 1)Q + P. Suppose there exist rational points Q, P such that G ~ (m — 1)Q + P 
and P,Q i D. Let G' = {m - l)Q + P. Then the codes Gn{D, G) and Gn{D, G') are equivalent [31, 
Proposition 2.2.14]. And the dual codes G^{D,G) and G^{D,G') are also equivalent. Here two linear 
codes Gi, G2 C F^ are said to be equivalent if there is a vector a = (ai, ■ ■ ■ , a„) E (F*)" such that 

G2 = a ■ Gi = {(aici, ■ ■ ■ , anCn) \ (ci, ■ ■ ■ , c„) G Gi} . 

It is easy to see that two equivalent codes have the same stopping sets and hence the same stopping set 
distributions. So to study the stopping sets and the stopping set distribution of Gq{D,G), it suffices to 
determine all the stopping sets and the stopping set distribution of Gq{D , (m — 1)Q + P). In this case, 
we use Q to define the group E{¥g) with the zero element Q. Then all results in this paper hold similarly 
for GniD, G) with G ~ (m - 1)Q + P such that P,Q ^ D. 

Note that g = I for elliptic curves. According to Corollary 7, any subset of [n] with cardinality ^ m + 2 
is a stopping set and any non-empty subset of [n] with cardinality ^ m — 1 is not a stopping set. So it is 
enough to consider the subsets of [n] with cardinality m and m+l. Below we use the group E(¥g) [27, 30] 
to give a description of these two classes of stopping sets with cardinality m and m + l, respectively. 

(i) Suppose A C [n] with cardinality m + 1 is not a stopping set. Then there are some i E A and 



/ G ^(G) such that 



Note that 



and 



jeA\{i} jeA 

deg(G — yj Pj) = m — m = , 

jeA\{i} 

div(/)^-G+ Yl P^- 

jeA\{i} 

Since both sides have degree zero, so 

div(/) = -G+ Y. p^= E ^p^-0)- 

jeA\{i} jeA\{i} 

In this case, AC [n], ^A = m + 1, is not a stopping set if and only if there exists some i E A such that 
the sum J^jeAUi} ^i ^'^ ^he group E{¥q) is O. 

(ii) Suppose A C [n] with cardinality m is a stopping set. By Theorem 6, for any i G A, we have 

•^{G- Y P,)=^{G-Yp^)- 

jeA\{i} jeA 

But 

deg(G- Y ^,) = 1>2(?-1 = 1, 

jeA\{i} 

by the Riemann-Roch theorem, there exists some / G Fg(_E) such that 

O^fe^G- Y Pj)=nG-YP^)- 

jeA\{i} jeA 

So 

div{f) = G-YP^ = Y.(0-P,). 

j&A j&A 

This is equivalent to 

jeA 
in the group E(¥g). Conversely, let A C [n] with cardinality m such that XljeA-^i ~ G. Since the zero 
divisor fi' = is a canonical divisor for elliptic curves, we have 

K-G + Y^J^^ ■ 

jeA 

By Corollary 9, A is a stopping set. 

From the argument above, we obtain the following partial results of the main theorem in the introduction. 



10 

Theorem 10. Let E be an elliptic curve over the finite field Fg, D = {Pi,P2,- ■ ■ ,Pn} <3 subset of E{¥q) 
such that the zero element O ^ D and let G = mO (0 < m < n). The non-empty stopping sets of the 
residue code Cq{D,G) are given as follows: 

(i) Any subset of [n] with cardinality ^ m — 1 is not a stopping set. 

(ii) Any subset of [n] with cardinality ^ m + 2 is a stopping set. 

(iii) A C [n], ^A = m + 1, is a stopping set if and only if for all i E A, the sum 

j€A\{i} 

(iv) AC [n], ^A = m, is a stopping set if and only if 

j&A 

Let us give an example to illustrate the theorem. 
Example 11. Let E be an elliptic curve defined over F5 by the equation 

y'^ = x^ + X + \ . 

Then E has 9 rational points: the infinity point O and Pi = (0, 1), P2 = (4, 2), P3 = (2, 1), P4 = (3, 4), 
P5 = (3, 1), Pe = (2, -1), Py = (4, -2), Pg = (0, -1). Using Group Law Algorithm 2.3 in [30], one can 
check that -^(Fs) forms a cyclic group with Pj = [i]Pi. Let D = {Pi, P2, ■ ■ ■ , Ps} and G = 30. 
By Corollary 9 and Theorem 10, all nonempty stopping sets of Cq{D,G) are given as follows: 
(i) subsets of [n] with cardinality ^ 5; 

(ii) {1,2,3,7}, {1,2,3,8}, {1,2,4,5}, {1,2, 4,7}, {1,2,4,8}, {1,2,5,7}, {1,2,5,8}, {1,2,7,8}, {1,3,4,6}, 
{1,3,4,7}, {1,3,4,8}, {1,3,6,7}, {1,3,6,8}, {1,4,5,6}, {1,4,5,7}, {1,4,5,8}, {1,4,6,7}, {1,4,7,8}, 
{1,5,6,8}, {1,5,7,8}, {1,6,7,8}, {2,3,5,6}, {2,3,5,7}, {2,3,5,8}, {2,3,6,7}, {2,3,6,8}, {2,4,5,6}, 
{2,4,5,7}, {2,4,5,8}, {2,4,6,7}, {2,4,7,8}, {2,5,6,8}, {2,5,7,8}, {2,6,7,8}, {3,4,5,6}, {3,4,5,7}, 
{3,4,5,8}, {3,4,6,7}, {3,5,6,8}, {4,5,7,8}; 
(iii) {1,2,6}, {1,3,5}, {2,3,4}, {3,7,8}, {4,6,8}, {5,6,7}. 
So the stopping set distribution of Gq{D, G) with the parity-check matrix H* is 

'1, ifi = 0, 
6, if ? = 3, 
Ti{H*) = \ 40, if i = 4, 

0, otherwise. 
Also, the minimum distance of the code Cq{D, G) is 3 by Proposition 1. 

Theorem 10 describes all the stopping sets of residue AG codes from elliptic curves. Next, we establish 



11 



the relationship between the set of stopping sets with cardinality m and the set of stopping sets with 
cardinality m + 1. 

Denote by S{m) and S{m + l) the two sets of stopping sets with cardinality m and m + 1 in the cases 
(iv) and (iii) in Theorem 10, respectively. Let S^{m) be the extended set of S{m) defined as follows 

S+{m)= [j {AU{i}:ie[n]\A} . 

AgS{m) 

Theorem 12. Notation as above. We have 

S{m + 1) n S+{m) = , 

and 

S{m + 1) = {all subsets of [n] with cardinality m + 1}\ S^{m) . 

Moreover, the union in the definition of S^ {m) is a disjoint union. Hence 

#^(m+l) = (jJ-#5+(m) 

= Ui)-(^-m)#5(m). 

Proof: First, S{m + 1) fl S^{m) = is obvious by parts (iii) and (iv) of Theorem 10. So 

S{m + 1) C {all subsets of [n] with cardinality m + 1} \ S^{m). 

On the other hand, for any A ^ S{m + 1) and ^A = m + 1, by Theorem 10 (iii), there is some i E A 
such that EieA\{i} Pj = O. By Theorem 10 (iv), A\{i} e S{m). So 

A= {A\{i])yj{i] eS+{m) . 

Hence 

S{m + 1) = {all subsets of [n] with cardinality m + 1} \ S^{m) . 

If there exist A G S{m), A' G S{m), i ^ A and i' ^ A' such that 

Ayj{i] = A'yj{i'}eS+{m) . 

Then we have i e A' , i' e A and A \ {%'} = A' \ {i}. 
Since 

jeA jeA' 

we get Pi = Pi'. So 

A = A\ i = i' . 



12 



That is, the union in the definition of S^{m) is a disjoint union. And the formula 



#5(m + l) = Ui)-#5 



^^m) 



Ui)-(^-^)#^( 



m] 
follows immediately. ■ 

Remark 13. The above theorem shows how we can get S{m + 1) from S{m). Conversely, if we know 
S{m + 1), then by the above theorem, we can exclude S{m + 1) from the set of all subsets of [n] with 
m+ 1 elements to get S^{m). For any / G S^{m), we calculate Y^iei ^i- Then by Theorem 10 (iv), there 
is some index j{I) E I such that 

i&I 

By the definitions of S{m) and S^{m), we have 

S{m) = {I\{j{I)}\IeS+{m)} . 

In the above example, by Theorem 10 (iv), S'(3) consists of all the subsets of [8] whose sums have 9 
as a divisor. Then by Theorem 12, S'(4) follows immediately from S'(3). 

The following corollary follows immediately from Proposition 1, Theorems 10 and 12. 

Corollary 14. Notation as above. The minimum distance and the stopping distance of the residue AG 
code Cq{D,G) is deg(G') or deg(G') + 1. More explicitly, if ij^Sim) > 0, then we have the stopping 
distance 

siCniD, G)) = d{Cn{D, G)) = m = deg(G') . 

If i^S{m) = 0, then we have i^S{m + 1) > and hence 

s{Cn{D, G)) = d{Cn{D, G)) = m + 1 = deg(G) + 1 . 

Let Q be an abelian group with zero element O and D a finite subset of Q. For an integer < A; < |D| 
and an element b E D we denote 

Ng{k,b,D) = j^{S<ZD\i^S = k and ^x = b} . 

xes 

Computing Ng{k,b,D) is called a counting version of the k-subset sum problem (A;-SSP). In general, a 
counting k-SSF is NP-hard [4]. If there is no confusion, we simply denote 

N{k,b,D) = Ng{k,b,D) . 

Remark 15. By the above theorem, for a general subset D C E(¥g), to decide whether ^S{m) > is 
the decision m-subset sum problem in E(¥g). It is known that the decision m-subset sum problem in 
E{¥q) in general is NP-hard under RP-reduction [3]. So to compute the stopping distance of Cn{D, G) 



13 



is NP-hard under RP-reduction. 

But for a subset D C E(¥g) with special algebraic structure, it is possible to give an explicit formula for 
^S{m) = N(m, O, D), and hence explicit formulae for #S'(m+l) and the whole stopping set distribution 
by Theorem 12. In the following, we consider special subsets D = P \ {0} for some subgroup P of 
E(¥q). In particular, recall that Cn{D, G) is called the standard elliptic code if D = E(¥g) \ {O}. 

Proposition 16 ([19, 23]). Let Q be a finite abelian group. For h eQ, we have 

N{^, b, G \ {0}) = ^ E ^-^^^^ {^u,~\ ■ ^ /^(^/^)#^M • 

s|cxp(g) V L / J / d| gcd(e(6),s) 

where N = ^Q, exp(^) is the exponent ofQ, e{h) = maxjrf | d\ exp(^), b G dQ}, /i is the Mobius function 
and Q[d] is the d-torsion subgroup of Q. 

Set ^ = P a subgroup of Ei¥q) in Proposition 16. Let A^ = |P| = n + 1 and D = P \ {O}. Then we 
have 

Theorem 17. The number of stopping sets of Cn{D,mO) with cardinality m is 

s|exp(P) V L / J / ^1^ 

So together with Theorems 10 and 12, we obtain Theorem 5. 

It is well-known that the group E(¥q) of rational points is isomorphic to 

E(¥g) ^ Z/miZ © Z/maZ , 

for some integers mi\m2. Then by Theorems 10, 12 and 17, we can determine the stopping set distribution 
of the standard residue AG code CQ{D,mO) from any elliptic curve E/¥g provided that we know the 
group structure of E{¥q). Explicitly, we can compute #5'(3) in Example 11: 

#^(3) = I E.|9(-1)'^L!J (9/-1) E,|,^(s/rf) \Z/9Z[d]\ 
= |(© + (D(3-l)-(9-3))=6. 

So #5(4) = (^) — (8 — 3)#S'(3) = 40. This agrees with the exhausting calculation in Example 11. 
If we take special subgroups of E(¥g), then we have the following corollary. 

Corollary 18. Notations as above. 
(i) If we take 

P ^ Z/p*Z 



14 



for some prime integer p and integer t ^ 1, then 

[logp{m)J 



In particular, if t = 1, then 



#^M = ^((''^^) + (-ir(p-i)) 



Ift = 2, then 



mm) = \[i^J) + (-i)™(/ -p) + (-ir^^^ -(p- !)(%/ 



p ■ 



(ii) //'we tofe 

P^ 'L/p^'"L®'L/p^^'L 

for some prime integer p and integers 1 ^ ti ^ t2, then 

t2 






f i+rahi{i,t\} _ j-l+min{i-l,ti}^ 

'- \ \ in I ' — ■ v I -T I / 

(iii) If we take 



for two distinct prime integers pi,P2 and integers ti,t2 ^ 1. then 



#s{m) = -^ I e^f -^) + (pi - i)(p, - 1) ■ E E(-i)"^^^^>^^VrvrH^'"L'i:;-') 



+E(-ir^*\'-;i?-')(P5-pr')+E5i,(-ir^3\''K")(rf-rf"; 

2 = 1 Pi p^ 

IV. Conclusion 

In this paper, we study stopping sets and stopping set distributions of residue algebraic geometry 
codes Cn{D,G). Two descriptions of stopping sets of residue algebraic geometry codes are presented. 
In particular, there is a gap deg(G') — 2g + 2 ^ i ^ deg(G) + 1 where in general we do not know 
whether a subset with cardinality i is a stopping set or not. In the case g = 0, there is no gap and we 
have a complete understanding. In the case g = I, using the group structure of rational points of elliptic 
curves, we can characterize all the stopping sets of algebraic geometry codes from elliptic curves. Then 
determining the stopping sets, the stopping set distribution and the stopping distance of Cn{D,G) are 
reduced to deg(G')-subset sum problems in finite abelian groups. In the case g > I, only partial results 
can be obtained. It is still not known how to compute the stopping set distribution. For further work, there 
are two interesting problems: 



15 

(i) There are some papers contributing to compute the stopping redundancy of MDS codes [10, 12, 28]. 
For AG codes from elliptic curves, we have seen that the code is very closed to be MDS, i.e., MDS or 
near-MDS [29] (an [n, k, d] linear code is called near-MDS if d = n — k and the dual distance d-^ = k). 
So how about the stopping redundancy of AG codes from elliptic curves? 

(ii) In this paper, we have determined the stopping set distributions of AG codes from elliptic curves 
with the parity-check matrix H* . Can we give optimal parity-check matrices for AG codes from elliptic 
curves? 

References 

[1] K.A.S. Abdel-Ghaffar and J.H. Weber. Complete enumeration of stopping sets of full-rank parity- 
check matrices of Hamming codes. IEEE Transactions on Information Theory, 53(9):3 196-3201, 
Sept. 2007. 

[2] R. Ahlswede and H. Aydinian. On generic erasure correcting sets and related problems. IEEE 
Transactions on Information Theory, 58(2):501-508, 2012. 

[3] Q. Cheng. Hard problems of algebraic geometry codes. IEEE Transactions on Information Theory, 
54:402-406, 2008. 

[4] T.H. Cormen, C. Stein, R.L. Rivest, and C.E. Leiserson. Introduction to Algorithms. McGraw-Hill 
Higher Education, 2nd edition, 2001. 

[5] C. Di, D. Proietti, I.E. Telatar, T.J. Richardson, and R.L. Urbanke. Finite-length analysis of low- 
density parity-check codes on the binary erasure channel. IEEE Transactions on Information Theory, 
48(6): 1570-1579, Jun. 2002. 

[6] M. Esmaeili and M.J. Amoshahy. On the stopping distance of array code parity-check matrices. 
IEEE Transactions on Information Theory, 55(8):3488-3493, Aug. 2009. 

[7] M. Esmaeili, M.H. Tadayon, and T.A. Gulliver. More on the stopping and minimum distances of 
array codes. IEEE Transactions on Communications, 59(3):750-757, 2011. 

[8] T. Etzion. On the stopping redundancy of Reed-MuUer codes. IEEE Transactions on Information 
Theory, 52(ll):4867-4879, Nov. 2006. 

[9] J. Feldman, M.J. Wainwright, and D.R. Karger. Using linear programming to decode binary linear 
codes. IEEE Transactions on Information Theory, 51(3):954-972, Mar. 2005. 
[10] J. Han and RH. Siegel. On the stopping redundancy of MDS codes. In IEEE International Symposium 

on Information Theory, 2006, pages 2491-2495, July 2006. 
[11] J. Han and RH. Siegel. Improved upper bounds on stopping redundancy. IEEE Transactions on 

Information Theory, 53(1):90-104, Jan. 2007. 
[12] J. Han, RH. Siegel, and R.M. Roth. Single-exclusion number and the stopping redundancy of MDS 
codes. IEEE Transactions on Information Theory, 55(9):4155-4166, Sept. 2009. 



16 

[13] J. Han, P.H. Siegel, and A. Vardy. Improved probabilistic bounds on stopping redundancy. IEEE 

Transactions on Information Theory, 54(4): 1749-1753, Apr. 2008. 
[14] T. Hehn, O. Milenkovic, S. Laendner, and J.B. Huber. Permutation decoding and the stopping 

redundancy hierarchy of cyclic and extended cyclic codes. IEEE Transactions on Information Theory, 

54(12):5308-5331, Dec. 2008. 
[15] H.D.L. HoUmann and L.M.G.M. Tolhuizen. Generic erasure correcting sets: Bounds and construc- 
tions. Journal of Combinatorial Theory, Series A, 113(8): 1746-1759, 2006. Special Issue in Honor 

of Jacobus H. van Lint. 
[16] H.D.L. HoUmann and L.M.G.M. Tolhuizen. On parity-check collections for iterative erasure decoding 

that correct all correctable erasure patterns of a given size. IEEE Transactions on Information Theory, 

53(2):823-828, Feb. 2007. 
[17] Y. Jiang, S.-T. Xia, and F.-W. Fu. Stopping set distributions of some Reed-MuUer codes. IEEE 

Transactions on Information Theory, 57(9):6078-6088, Sept. 2011. 
[18] N. Kashyap and A. Vardy. Stopping sets in codes from designs. In Proceedings: IEEE International 

Symposium on Information Theory, 2003., page 122, June-4 July 2003. 
[19] M. Kosters. The subset sum problem for finite abelian groups. Journal of Combinatorial Theory, 

Series A, 120(3):527-530, 2013. 
[20] K.M. Krishnan and P. Shankar. Computing the stopping distance of a Tanner graph is NP-hard. 

IEEE Transactions on Information Theory, 53(6):2278-2280, Jun. 2007. 
[21] S. Laendner and O. Milenkovic. LDPC codes based on latin squares: Cycle structure, stopping set, 

and trapping set analysis. IEEE Transactions on Communications, 55(2):303-312, Feb. 2007. 
[22] J.Y. Li and D. Wan. On the subset sum problem over finite fields. Finite Fields and Their Applications, 

14(4):91 1-929, 2008. 
[23] J.Y. Li and D. Wan. Counting subset sums of finite abelian groups. Journal of Combinatorial Theory, 

Series A, 119(1):170-182, 2012. 
[24] H. Liu, Y Li, L. Ma, and J. Chen. On the smallest absorbing sets of LDPC codes from finite planes. 

IEEE Transactions on Information Theory, 58(6):4014-4020, 2012. 
[25] A. McGregor and O. Milenkovic. On the hardness of approximating stopping and trapping sets. 

IEEE Transactions on Information Theory, 56(4): 1640-1650, 2010. 
[26] A. Orlitsky, K. Viswanathan, and J. Zhang. Stopping set distribution of LDPC code ensembles. IEEE 

Transactions on Information Theory, 51(3):929-953, Mar. 2005. 
[27] R. Schoof. Nonsingular plane cubic curves over finite fields. J. Comb. Theory, Ser A, 46(2): 183-211, 

1987. 
[28] M. Schwartz and A. Vardy. On the stopping distance and the stopping redundancy of codes. IEEE 

Transactions on Information Theory, 52(3):922-932, Mar. 2006. 



17 

[29] M.A. ShokroUahi. On the weight distribution of elliptic codes. Research report: Institut fur Informatik. 

Inst, fiir Informatik, 1990. 
[30] J.H. Silverman. The Arithmetic of Elliptic Curves, volume 106 of Graduate Texts in Mathematics. 

Springer, Dordrecht, second edition, 2009. 
[31] H. Stichtenoth. Algebraic Function Fields and Codes, volume 254 of Graduate Texts in Mathematics. 

Springer- Verlag, Berlin, second edition, 2009. 
[32] R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 

27(5):533-547, Sep. 1981. 
[33] T. Wadayama. Average stopping set weight distributions of redundant random ensembles. IEEE 

Transactions on Information Theory, 54(1 1):499 1-5004, Nov. 2008. 
[34] J.H. Weber and K.A.S. Abdel-Ghaffar. Stopping set analysis for Hamming codes. In IEEE 

Information Theory Workshop, 2005, pages 244-247, Aug.-l Sept. 2005. 
[35] S.-T. Xia and F.-W. Fu. On the stopping distance of finite geometry LDPC codes. IEEE 

Communications Letters, 10(5):38 1-383, May 2006. 
[36] S.-T. Xia and F.-W. Fu. Stopping set distributions of some linear codes. In IEEE Information Theory 

Workshop, 2006. ITW '06 Chengdu, pages 47-51, Oct. 2006.